package leetcode;

public class _0033 {
    /**
     * 搜索旋转排序数组
     */
    class Solution {
        public int search(int[] nums, int target) {
            int n = nums.length;
            int i = finMin(nums);
            if(target>nums[n-1]){
                return lowerBound(nums,0,i,target);
            }
            return lowerBound(nums,i,n-1,target);
        }
        public int lowerBound(int[] nums,int left,int right,int target){
            int t = right;
            while(left<=right){
                int mid = left+(right-left)/2;
                if(nums[mid]<target){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
            if(left<=t&&nums[left]==target){
                return left;
            }
            return -1;
        }
        public int finMin(int[] nums){
            int n = nums.length;
            int left = 0;
            int right = n-2;
            while(left<=right){
                int mid = left+(right-left)/2;
                if(nums[mid]>nums[n-1]){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
            return left;
        }
    }
}
